/**
 * @program: LeetCode
 * @description: LeetCode :剑指 Offer II 089. 房屋偷盗
 * @author: WXY
 * @create: 2023-01-02 20:51
 * @Version 1.0
 **/
public class Num_offer2_089_ {
    public int rob(int[] arr) {
        if (arr.length <= 0) return 0;
        if (arr.length == 1) return arr[0];
        if (arr.length == 2) return Math.max(arr[0], arr[1]);
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
        int max = Math.max(dp[0], dp[1]);
        for (int i = 2; i < arr.length; i++) {
            dp[i] = Math.max(dp[i - 1], arr[i] + dp[i - 2]);
            max = Math.max(max, dp[i]);
        }
        return max;
    }

}
